\documentclass{cours}

\title{\textsc{Programmation fonctionnelle}}
\author{Notes prises d'après le cours de M. \'Eric Violard}
\date{Université de Strabourg}

\begin{document}

\chapter{Introduction}
\minitoc
\section{Modèle de programmation}
Chacun des modes de programmation fondamentaux (impératif, fonctionnel ou
logique) est bâti sur un modèle mathématique pour exprimer la relation entre
données et résultats.

\subsection{Modèle logique}
En programmation logique, la relation est donnée par des connecteurs logiques.
Le programme consiste en une formule logique. L'exécution revient à construire
la preuve. Par exemple, en prolog :
\begin{verbatim}
max(A,B,M):- A>=B, M=A.
max(A,B,M):- B>=A, M=B.
\end{verbatim}

\`A l'exécution de ce programme, on aura :
\begin{verbatim}
|?-max(2,7,M).
    2>=7 ? fail
    7>=2 ?
    M=7
\end{verbatim}

\subsection{Modèle fonctionnel}
En programmation fonctionnelle, la relation est restreinte à une fonction. Le
programme se résume à une composition de fonctions. L'exécution elle, est
l'application de la fonction. Par exemple, en Caml :
\begin{verbatim}
let max(a,b)=if a>=b then a else b;;
\end{verbatim}

\'A l'exécution de ce programme, on aura :
\begin{verbatim}
# max(2,7);;
 if 2>=7 then 2 else 7
=if false then 2 else 7
=7
\end{verbatim}

\subsection{Modèle impératif}
Le modèle impératif est plus complexe et atypique. Ici, on modélise les états
mémoire. Le programme est donc une fonction de transition d'un état mémoire
initial vers un état mémoire final, par une séquence d'affectations. L'exécution
correspond à une séquence d'affectations. Par exemple, en C :
\begin{verbatim}
m=a ;
if(b>=a) m=b;
return m;
\end{verbatim}

\`A l'exécution, on aura :

\begin{center}
\begin{tabular}{c c c}
État initial & & État final \\
\url{a} \quad  \url{2} & \url{2} & \url{2} \\
\url{b} \quad  \url{7} & \url{7} & \url{7} \\
\url{m} \quad  \url{-} & \url{2} & \url{7}
\end{tabular}
\end{center}

\section{Variables}
Tous ces modes de programmation utilisent des variables, mais le sens même du
mot "variable" diffère. En programmation fonctionnelle ou logique, une variable
à le même sens qu'en mathématiques : c'est une inconnue dans une équation.
Résoudre cette équation en donne une définition explicite.

En programmation impérative en revanche, une variable est l'expression abstraite
d'une adresse en mémoire. Une définition est appelé "affectation" est  signifie
le rangement d'une valeur à cette adresse.

\subsection{Propriété de transparence référentielle}
On pourrait définir la transparence référentielle de la façon suivante :

\begin{quotation}
\textit{Le résultat d'un programme ne change pas si on remplace une expression
par une autre expression de valeur égale}
\end{quotation}

Cette propriété est vraie en programmation fonctionnelle, mais pas en
programmation impérative par exemple, ce qui est à l'origine de nombreuses
difficultés de programmation. D'une manière plus générale, on dit qu'un élément
de langage est dit "impur" si il contredit d'une manière ou d'une autre la
propriété de transparence référentielle. Dans ce cours, nous utiliserons le
langage OCaml débarrassé de ses éléments impurs (l'affection, les variables au
sens impératif, les tableaux, le pointeurs...).

\section{Comparaison de la programmation fonctionnelle à l'impérative}
La programmation fonctionnelle présente plusieurs avantages en comparaison à a
programmation impérative :

\begin{itemize}
\item elle présente une puissance d'expression (concision, abstraction, types
algébriques...)
\item facilité de programmation (interprète, contrôleur de type, gestion de la
mémoire laissée au compilateur...)
\end{itemize}

En revanche, le code exécutable présente une efficacité moindre en termes de
performances moyennes comparables.

\section{Programmer avec des fonctions}
En mathématiques, une fonction $f$ fait correspondre à chaque élément d'un
ensemble $A$, appelé domaine de la fonction, dans un autre ensemble $B$, appelé
codomaine de la fonction, et on note : $f : A \longrightarrow B$ 

Une manière élégante consiste à utiliser une équation, ou règle de
correspondance, d'un élément du domaine vers le codomaine. Une fonction complexe
peut être définie comme une composition de fonctions plus simples.

\section{Quelques facilités en OCaml}
\subsection{Fonctions anonymes}
En maths, on peut utiliser une fonction sans pour autant la nommer. En OCaml, on
peut également le faire en utilisant le mot-clef \url{fonction} :
\begin{verbatim}
#function x → 2*x+1;;
-:int → int = <fun>
#(function x → 2*x+1)(1);;
-:int = 3
\end{verbatim}

\subsection{Définition temporaire}
En maths, on introduit parfois une variable pour simplifier l'expression
du résultat. En OCaml, on peut le faire en utilisant la commande \url{let}...
\url{in} :
\begin{verbatim}
#let moyenne (a, b) = let somme = a+b in somme/2;;
val moyenne:int*int → int = <fun>
\end{verbatim}

Attention : une définition avec \url{let} est permanente, alors qu'une
définition avec \url{let}...\url{in} \url{E} est temporaire : elle ne dure que
le temps du calcul de \url{E}.

\chapter{Récursivité}
\minitoc
\section{Définition}
<need def>

On peut par exemple définir une fonction qui calcule la somme des $n$ premiers
entiers de façon récursive. En remarquant que cette somme peut être définie à
partir de la somme des $n-1$ premiers entiers et en opérant par décomposition
des cas, on arrive à :
\begin{verbatim}
somme(0)=0
somme(n)=somme(n-1)+n, n>0
\end{verbatim}

Cette définition à ceci de remarquable, elle fait appel à la fonction qu'elle
définit. On parle de définition récursive, et \url{somme(n-1)} est un appel
récursif. Il est important de préciser que \url{somme(0)=0} : sans cela, la
fonction n'est pas définie. Le cas $n=0$ est apellé cas de base.

En OCaml, on peut définir de telles fonctions en utilisant le mot-clé \url{rec}:
\begin{verbatim}
let rec somme n = if n=0 then 0 else somme(n-1);;
\end{verbatim}

Inventer une définition récursive pour résoudre un problème donné, consiste
typiquement à:
\begin{itemize}
\item identifier des sous-problèmes de même nature et de taille inférieure,
\item supposer résolus, ces sous problèmes par autant d'appels récursifs,
\item montrer comment résoudre le problème en entier en combinant les solutions
partielles.
\end{itemize}

\paragraph{}
On retrouve ici le lien bien connu des théoriciens entre les preuves et les
programmes. Cette démarche est aussi fructueuse pour contruire une
définition récursive et elle aide aussi à comprendre pourquoi une fonction
récursive ne donne pas le résultat attendu ou ne se termine pas.

\subsection{Définition récursive et terminaison}
Les logiciens Gödel et Turing ont démontré dans les années 1930 qu'il n'était
pas possible de trouver un programme sachant tester si une fonction récursive
termine son calcul ou pas. Autrement dit, l'arrêt du calcul est indécidable.

\subsection{Terminaison et domaine}
Une fonction ne doit pas être appliquée sur une valeur qui n'appartient pas à
son domaine. Dans le cas contraire, la fonction donne un résultat indéterminé ou
ne termine pas.

\section{Domaine et type}
Il ne faut pas confondre le domaine et le type de l'argument d'une fonction.
Généralement, le domaine est seulement un sous-ensemble de l'ensemble des
valeurs du type de l'argument.

Nous verrons d'autres définitions récursives dans la suite du cours. C'est une
construction largement employé en programmation fonctionnelle.

La récursivité conduit à des programmes concis et élégants. Mais sa puissance
deviendra plus apparente lorsque nous considérerons des fonctions sur des types
structurés.

\chapter{Types}
\minitoc

En comparaison des langages impératifs, les langages fonctionnels
offrent une vue plus abstraite des types. En programmation impérative, 
le type est directement lié à la représentation des données en mémoire. 
En programmation fonctionnelle en revanche, le type est déduit des opérations 
qui s'appliquent sur les variables.

OCaml est un langage dit \textit{fortement typé} : toute expression du
langage admet un type. Ce type est déduit avant l'exécution,
statiquement. Par exemple :
\begin{verbatim}
#let circonference(r)= 2. *. 3.14 *. r;;
 val circonference : float -> float = <fun>
\end{verbatim}

D'autres langages fonctionnels plus anciens (comme LISP) le premier des
langages fonctionnels) sont seulement \textit{faiblement typés}. Le type
est déterminé au moment de l'exécution, dynamiquement. 

Cette approche ancienne ne permet au programmeur qu'une utilisation 
limitée de types. L'approche des langages fonctionnels récents inclut les 
notions de constructeurs, de calculs ou d'inférence de types, définissant 
ainsi une véritable théorie des types et un procédé de programmation par 
filtrage. Nous allons ici détailler toutes ces notions.


\end{document}
